           BOI.3. (Lan aditiv). O secven[ de numere ntregi pozitive a1,a2,
..,an se numete lan aditiv de lungime n dac[, pentru orice k(1<kn), exist[
i i j, 1ij<k n aa fel ca ak=ai+aj. Scriei un program care, pentru a1=1
i ultimul element citit de la intrare, g[sete un lan aditiv de lungime minim[.
Exemplu: Pentru intrarea
4
un r[spuns posibil poate fi
1 2 4
========================================
          BOI 3 (Adrian Atanasiu):
           Se genereaz[ toate puterile lui 2 pn[ la n; ele vor intra n irul aditiv.
In faza a doua, toate puterile lui 2 care apar efectiv n scrierea lui n sunt colectate
separat n vectorul aux; sumele lor dou[ cte dou[ ncepnd cu cele mai mici sunt
introduse n ir. Ceea ce se obine n final se ordoneaz[ cresc[tor.
           Dac[ n este o putere a lui 2, el va apare n ir din faza de generare a
puterilor lui 2; altfel, va fi obinut ca ultima sum[ din aux;
Atenie ! Algoritmul nu este bun pentru numerele de forma n=2k-1, pentru care se
obine un ir mai lung cu un termen dect unul minim.
           In acest caz s-a folosit urm[toarea idee - valabil[ pentru n>7, n=2k-1:
- primele k-1 elemente din a sunt a[1]=20,a[2]=21,..,a[k-1]=2k-2;
- urmeaz[ dou[ elemente calculate deosebit: 
                             a[k]=a[k-1]+1; a[k+1]=2*a[k];
- fiecare element care urmeaz[ este calculat adunnd la precedentul num[rul care
urmeaz[ din secvena a[3],a[4],..,a[k-2];
- num[rul final 2k-1 se obine adunnd ultimul num[r din secven[ cu a[k].
   Este interesant de demonstrat matematic valabilitatea acestui algoritm.
program aditiv;
uses crt;
var
 a,aux,bin:array[1..20] of integer;
 n,m,term,i,j,k:integer;
-------------------------------------------------------------
procedure binar;
var
 p:integer;
begin
  term:=0; p:=n;
  while p>0 do begin
     term:=term+1; bin[term]:=p mod 2; p:=p div 2 end;
end;
-------------------------------------------------------
procedure ordonare;
var
   x:integer;
   schimba:boolean;
begin
   if term<m then
      repeat
       schimba:=true;
       for i:=1 to m-1 do
          if a[i]>a[i+1] then begin
             x:=a[i];a[i]:=a[i+1];a[i+1]:=x;schimba:=false end
      until schimba;
end;
------------------------------------------------------------
begin  {Program principal}
  clrscr;
  write('Dati numarul final n='); readln(n);
  binar;
  a[1]:=1;m:=term;
  if bin[1]=1 then begin j:=1; aux[1]:=1 end
                   else j:=0;
  for i:=2 to term do begin
     a[i]:=2*a[i-1];
     if bin[i]=1 then begin
        j:=j+1; aux[j]:=a[i] end end;
  if (j>1) and (j<term) then
        for i:=2 to j do begin
           aux[i]:=aux[i-1]+aux[i];
           m:=m+1; a[m]:=aux[i] end
                        else
            if (j=term) and (m>3) then begin
                a[m]:=a[m-1]+1;
                a[m+1]:=2*a[m];m:=m+2; i:=3;
                while i<=term-2 do begin
                    a[m]:=a[m-1]+a[i];i:=i+1;m:=m+1 end;
                a[m]:=a[m-1]+a[term] end
                            else
                if m=2 then begin m:=m+1;a[m]:=3 end
                       else if m=3 then begin
                           m:=m+2;a[m-1]:=3;a[m]:=7 end;
  ordonare;
  writeln('Sirul aditiv obtinut are ',m,' termeni:');
  for i:=1 to m do write(a[i],' ');
end.
--------------------------------------------
